package org.xiaoxin.leetcode.string;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 3. 无重复字符的最长子串
 * <p>
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 * <p>
 * 示例 1:
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * <p>
 * 示例 2:
 * 输入: s = "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * <p>
 * 示例 3:
 * 输入: s = "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 * 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 * <p>
 * 提示：
 * 0 <= s.length <= 5 * 10^4
 * s 由英文字母、数字、符号和空格组成
 * <p>
 * 难度：中等
 * 标签：哈希表、字符串、滑动窗口
 *
 * @author xiaoxin
 */
public class _003_LongestSubstringWithoutRepeatingCharacters {

    /**
     * 方法一：暴力解法
     * 思路：枚举所有的子串，判断子串中是否有重复字符
     * 时间复杂度：O(n³)，其中 n 是字符串的长度
     * 空间复杂度：O(min(n, m))，其中 n 是字符串的长度，m 是字符集的大小
     */
    public int lengthOfLongestSubstring1(String s) {
        // 提示：
        // 1. 枚举所有可能的子串
        // 2. 对每个子串，检查是否包含重复字符
        // 3. 如果不包含重复字符，更新最大长度
        int n = s.length();
        int maxLength = 0;


        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (allUnique(s, i, j)) {
                    maxLength = Math.max(maxLength, j - i + 1);
                }
            }
        }


        return maxLength;
    }

    private boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i <= end; i++) {
            char c = s.charAt(i);
            if (set.contains(c)) {
                return false;
            }
            set.add(c);
        }
        return true;
    }

    /**
     * 方法二：滑动窗口
     * 思路：使用滑动窗口，窗口内的字符都是不重复的
     * 时间复杂度：O(n)，其中 n 是字符串的长度
     * 空间复杂度：O(min(n, m))，其中 n 是字符串的长度，m 是字符集的大小
     */
    public int lengthOfLongestSubstring2(String s) {
        // 提示：
        // 1. 使用滑动窗口，窗口内的字符都是不重复的
        // 2. 使用 HashSet 存储窗口中的字符
        // 3. 右指针不断向右移动，如果没有重复字符，则加入集合
        // 4. 如果遇到重复字符，则左指针向右移动，并从集合中移除左指针指向的字符
        int length = s.length();
        int maxLength = 0, left = 0, right = 0;

        Set<Character> set = new HashSet<>();

        while (left < length && right < length) {
            if (!set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                right++;
                maxLength = Math.max(maxLength, right - left);
            } else {
                set.remove(s.charAt(left));
                left++;
            }

        }
        return maxLength;


    }

    /**
     * 方法三：优化的滑动窗口
     * 思路：使用哈希表记录字符最后出现的位置，遇到重复字符时直接跳过中间的字符
     * 时间复杂度：O(n)，其中 n 是字符串的长度
     * 空间复杂度：O(min(n, m))，其中 n 是字符串的长度，m 是字符集的大小
     */
    public int lengthOfLongestSubstring3(String s) {
        // 提示：
        // 1. 使用 HashMap 存储字符及其最后出现的位置
        // 2. 当遇到重复字符时，直接将左指针移动到该字符上次出现位置的下一位
        // 3. 这样可以避免方法二中的多次移动左指针
        int n = s.length();
        Map<Character, Integer> map = new HashMap<>();
        int maxLength = 0;

        for (int i = 0, j = 0; j < n; j++) {
            char ch = s.charAt(j);
            if (map.containsKey(ch)) {
            // 当遇到重复字符时,需要将左指针i移动到该字符上次出现位置的下一位
            // 但要确保i不会后退,所以取max
                i = Math.max(i, map.get(ch) + 1);
            }
            maxLength = Math.max(maxLength, j - i + 1);
            map.put(ch, j);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        testAllMethods();
    }

    /**
     * 测试所有方法
     */
    private static void testAllMethods() {
        System.out.println("=== 3. 无重复字符的最长子串 - 测试用例 ===\n");

        // 示例 1
        String s1 = "abcabcbb";
        testCase("示例 1", s1, 3);

        // 示例 2
        String s2 = "bbbbb";
        testCase("示例 2", s2, 1);

        // 示例 3
        String s3 = "pwwkew";
        testCase("示例 3", s3, 3);

        // 额外测试用例

        // 测试用例 4：空字符串
        String s4 = "";
        testCase("测试用例 4（空字符串）", s4, 0);

        // 测试用例 5：单个字符
        String s5 = "a";
        testCase("测试用例 5（单个字符）", s5, 1);

        // 测试用例 6：所有字符都不同
        String s6 = "abcdefg";
        testCase("测试用例 6（所有字符都不同）", s6, 7);

        // 测试用例 7：特殊字符
        String s7 = "!@#$%^&*()";
        testCase("测试用例 7（特殊字符）", s7, 10);

        // 测试用例 8：中文字符
        String s8 = "你好世界";
        testCase("测试用例 8（中文字符）", s8, 4);

        // 测试用例 9：最长子串在中间
        String s9 = "abcdcba";
        testCase("测试用例 9（最长子串在中间）", s9, 4);

        // 测试用例 10：最长子串在末尾
        String s10 = "aabcdef";
        testCase("测试用例 10（最长子串在末尾）", s10, 6);
    }

    /**
     * 测试单个用例
     */
    private static void testCase(String testName, String s, int expected) {
        System.out.println(testName + ":");
        System.out.println("输入: s = \"" + s + "\"");
        System.out.println("期望结果: " + expected);

        _003_LongestSubstringWithoutRepeatingCharacters solution = new _003_LongestSubstringWithoutRepeatingCharacters();

        // 测试方法一
        int result1 = solution.lengthOfLongestSubstring1(s);
        boolean method1Correct = result1 == expected;
        System.out.println("方法一结果: " + result1 + " " +
                (method1Correct ? "✅" : "❌"));

        // 测试方法二
        int result2 = solution.lengthOfLongestSubstring2(s);
        boolean method2Correct = result2 == expected;
        System.out.println("方法二结果: " + result2 + " " +
                (method2Correct ? "✅" : "❌"));

        // 测试方法三
        int result3 = solution.lengthOfLongestSubstring3(s);
        boolean method3Correct = result3 == expected;
        System.out.println("方法三结果: " + result3 + " " +
                (method3Correct ? "✅" : "❌"));

        boolean allCorrect = method1Correct && method2Correct && method3Correct;
        System.out.println("整体测试: " + (allCorrect ? "✅ 通过" : "❌ 失败"));
        System.out.println();
    }
}